jhcarl0814.github.io Augmented Containers Sequence augmented_*****_t augmented_deque_t augmented_sequence_t Associative augmented_***​/​***​/​********​/​********_t (has-a augmented_sequence_t) Graph
enum class augmented_graph_part_data_structure_e { top_tree, link_cut_tree, a_new_approach_to_dynamic_all_pairs_shortest_paths, fully_dynamic_planarity_testing_in_polylogarithmic_time, }; template< typename vertex_t, typename edge_t, typename parts_data_structure_and_parameters_t, std::strict_weak_order<vertex_t, vertex_t> compartor_vertex_t = std::less<vertex_t>, std::strict_weak_order<edge_t, edge_t> compartor_edge_t = std::less<edge_t>, typename allocator_vertex_t = std::allocator<vertex_t> > struct augmented_graph_t;
augmented_graph_t is an augmented, general-purpose graph. It's part of the augmented containers library, providing a more powerful version of containers (let containers (and possibly its subranges) always have several accompanying results of algorithms/views), as well as <algorithm> and <ranges> (when the input changes, refresh output values/ranges in logarithmic time complexity). To help understand what kind of problems the library solves: Dynamic problem (algorithms) - Wikipedia, Augmented map - Wikipedia.
Each vertex_t/edge_t(std::monostate) does not store any information. No parts are attached to the graph. Only structual information of the graph is maintained.
augmented_containers::augmented_graph_t< std::monostate, std::monostate, std::tuple<>, monostate_comparator_t, monostate_comparator_t > augmented_graph;
A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t(void) does not store any information. The internal operation does not suggest any tree edge to cut when inserted edge's 2 vertices belong to same tree. An arbitrary spanning forest of the graph is maintained, so circuit rank (cyclomatic number), a cycle basis and a feedback edge set of the graph can be answered quickly. Connected components of the graph and whether 2 vertices belong to same component can also be answered quickly, but note that there are faster data structures dedicated to maintaining connectivity information of graphs.
augmented_containers::augmented_graph_t< std::monostate, std::monostate, std::tuple< std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_empty_t<>> >, monostate_comparator_t, monostate_comparator_t > augmented_graph;
Each edge_t(int) stores the weight of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t(graph_t::it_edge_it_vertex_t) points to the maximum-weight edge among the cluster's path descendant edges.
When inserting an edge whose 2 vertices belong to same tree, augmented_graph_part_data_structure_e::top_tree exposes the 2 vertices (so the iterator pointing to the maximum-weight edge among the tree path's edges can be read from root cluster). get_top_tree_internal_operations_selecting_path_t selects the old edge for augmented_graph_part_data_structure_e::top_tree to cut before linking the new edge, or doesn't select any edge and augmented_graph_part_data_structure_e::top_tree just put the edge to the set of edges that do not belong to the forest.
get_top_tree_internal_operations_selecting_path_t let augmented_graph_part_data_structure_e::top_tree order the set of edges that do not belong to the forest in weight-increasing order, so that when eraseing a tree edge, augmented_graph_part_data_structure_e::top_tree look for replacement among the edges in weight-increasing order.
augmented_containers::augmented_graph_t< std::monostate, int, std::tuple< std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_selecting_path_t<std::less<void>>> >, monostate_comparator_t > augmented_graph;
Two augmented_graph_part_data_structure_e::top_trees are attached to the graph. Part-0 and part-1 maintain minimum spanning forest and maximum spanning forest of the graph respectively. Negating the comparator of minimum spanning forest configuration results in maximum spanning forest configuration.
augmented_containers::augmented_graph_t< std::monostate, int, std::tuple< std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_selecting_path_t<std::less<void>>>, std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_selecting_path_t<std::greater<void>>> >, monostate_comparator_t > augmented_graph;
Each vertex_t(bool) stores whether the vertex is marked. Each edge_t(int) stores the length of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t stores: tree path length between its 2 boundary vertices, the nearest marked vertices (among the cluster's descendant edges' vertices excluding the 2 boundary vertices) and distance to them for each its 2 boundary vertices. Quickly answers the nearest marked vertices to any vertex and its distance to them by exposeing the vertex and adding the information excluded. Quickly mark/unmark any vertex by exposeing the vertex (so that no cluster_t has the vertex as non-boundary descendant vertex) and updateing it. Quickly change the length of any edge by updateing it (the underlying top tree performs a cut and a link).
augmented_containers::augmented_graph_t< bool, int, std::tuple< std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_nearest_marked_vertices_t<int>> > > augmented_graph;
Each edge_t(int) stores the non-negative length of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t stores: tree path length between its 2 boundary vertices, eccentricity and 1 farthest vertex (through the cluster's descendant edges) for each its 2 boundary vertices, diameter and 2 farthest vertices (through the cluster's descendant edges). Quickly answers the eccentricity and 1 farthest vertex of any vertex by exposeing the vertex. Quickly answers the diameter and 2 farthest vertices of the graph because the information is stored in root cluster. Quickly change the length of any edge by updateing it (the underlying top tree performs a cut and a link).
augmented_containers::augmented_graph_t< std::monostate, int, std::tuple< std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_diameter_t<int>> >, monostate_comparator_t > augmented_graph;
Each vertex_t(int) stores the non-negative weight of the vertex. Each edge_t(int) stores the non-negative length of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t stores: tree path length between its 2 boundary vertices, distance-weighted weight sum of vertices (among the cluster's descendant edges' vertices excluding the 2 boundary vertices) for each its 2 boundary vertices, weight sum of vertices (among the cluster's descendant edges' vertices excluding the 2 boundary vertices). Quickly answers the median of the graph by non_local_searching choosing sub-cluster having larger weight sum of vertices (including its 2 boundary vertices) each round, exposeing the 2 vertices of the result edge and adding the information excluded. Quickly change the weight of any vertex by exposeing the vertex (so that no cluster_t has the vertex as non-boundary descendant vertex) and updateing it. Quickly change the length of any edge by updateing it (the underlying top tree performs a cut and a link).
augmented_containers::augmented_graph_t< int, int, std::tuple< std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_median_t<int>> > > augmented_graph;
Each edge_t(int) stores the positive length of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t stores tree path length between its 2 boundary vertices. Quickly answers: along the tree path between any 2 vertices, edge including any number (each edge includes range [0,l1), [l1,l1+l2), ..., or each edge includes range (0,l1], (l1,l1+l2], ...) starting from one of the vertex, by exposing the 2 vertices and searching among path descendant sub-clusters between the 2 vertices. Quickly answers the intersection vertex of any 3 vertices by exposing each of 3 vertex pairs and reading tree path length between each vertex pair from the root cluster, along the tree path between v1 and v2 calculating the 2 edges including number (d12+d13-d23)/2 using left-inclusive-right-exclusive view and left-exclusive-right-inclusive view respectively (the intersection vertex is the common vertex of the 2 edges). Quickly change the length of any edge by updateing it (the underlying top tree performs a cut and a link).
augmented_containers::augmented_graph_t< std::monostate, int, std::tuple< std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_distance_t<int>> >, monostate_comparator_t > augmented_graph;